package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName _77组合
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2021/10/8 19:58
 * Version 1.0
 **/
public class _77组合 {
    /*List<Integer> list = new ArrayList<>();
    ArrayList<List<Integer>> lists = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        getCombine(1,n,k);
        return lists;
    }
    public void getCombine(int start,int end,int k){
        if(list.size() == k){
            lists.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i <= end - (k - list.size()) + 1; i++){//剪的妙！！！
            list.add(i);
            getCombine(i+1,end,k);
            list.remove(list.size() -1);
        }
    }*/
    List<Integer> res = new ArrayList<>();
    List<List<Integer>> ress = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        getcombine(n,0,k);
        return ress;
    }
    public void getcombine(int n, int start, int k){
        if(res.size() == k){
            ress.add(res);
        }
        for(int i = start; i < n; i++){
            res.add(i);
            getcombine(n,i + 1,k);
            res.remove(res.size() - 1);
        }
    }
}
